package com.zlk.algorithm.algorithm.dimidiate;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName PartMin
 * @description: 局部最小值问题
 * 局部最小值问题 定义何为局部最小值： arr[0] < arr[1]，0位置是局部最小；
 * arr[N-1] < arr[N-2]，N-1位置是局部最小； arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；
 * 给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回
 * @author: slfang
 * @create: 2023-12-21 15:22
 * @Version 1.0
 **/
public class PartMin {



    /**
     * arr[0] < arr[1]，0位置是局部最小；
     * arr[N-1] < arr[N-2]，N-1位置是局部最小；
     * arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；
     * 给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回
     * @return
     */
    private int partMin(int[] arr) {
        if(arr==null||arr.length<1){
            return -1;
        }
        int l = 0;
        int r = arr.length-1;
        if(arr.length==1){
            return 0;
        }
        if(arr[l]<arr[l+1]){
            return l;
        }
        if(r<arr[r-1]){
            return r;
        }
        //走到这个位置说明上述两边都不是局部最小值，所以再趋势再[0,len-1]中间肯定是存在局部最小的
        int mid=-1;
        while (l<=r){
            mid = l+(r-l)>>1;
            int leftVal = arr[mid-1];
            int rightVal = arr[mid+1];
            if(arr[mid]<leftVal&&arr[mid]<rightVal){
                return mid;
            }
            if(arr[mid]<leftVal){//意思就是左到右趋势是变小的
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return mid;
    }

    public static void main(String[] args) {
        //System.out.println(findPeakElement(new int[]{1, 2, 3, 1}));
        System.out.println(findPeakElement(new int[]{3,4,3,2,1}));
    }


    //https://leetcode.cn/problems/find-peak-element/

    public static int findPeakElement(int[] nums) {
        int[] arr = nums;
        int l = 0;
        int r = arr.length-1;
        if(arr.length==1){
            return 0;
        }
        if(arr[l]>arr[l+1]){
            return l;
        }
        if(arr[r]>arr[r-1]){
            return r;
        }
        //走到这个位置说明上述两边都不是局部最小值，所以再趋势再[0,len-1]中间肯定是存在局部最小的

        l++;
        r--;
        int mid=-1;
        while (l<=r){
            mid = l+((r-l)>>1);
            int leftVal = arr[mid-1];
            int rightVal = arr[mid+1];

            if(arr[mid]<leftVal){//意思就是左到右趋势是变小的
                r = mid-1;
            }else if(arr[mid]<rightVal){
                l = mid+1;
            }else{
                return mid;
            }
        }
        return mid;
    }

}
